Algorytm Neville’a

Algorytm Neville’a – algorytm zaproponowany przez angielskiego matematyka Erica Harolda Neville’a. Jest używany do wyznaczania wartości wielomianu interpolacyjnego (Lagrange’a i Newtona) w danym punkcie $x.$ Ideą jest wyznaczenie rozwiązania w krokach od pojedynczych węzłów do całego ich zbioru.

Biorąc pod uwagę zbiór danych punktów węzłowych $(x_{i},y_{i}),i=1,2,\dots ,n,$ wielomian $P$ jest stopnia nie wyższego niż $n,$ a jego wartości w punktach węzłowych są takie same jak wartości interpolowanej funkcji:

P(x_{i})=f(x_{i})=y_{i},

dla

i=1,\dots ,n+1.

Definiujemy wielomiany interpolacyjne i ich wartości w ustalonym punkcie $x.$

$p_{i}$ – wartość, w punkcie $x,$ wielomianu stopnia zerowego przechodzącego przez punkt $(x_{i},y_{i}){:}$

p_{i}=y_{i}=P_{i}(x)

dla

i=0,\dots ,n.

$p_{i(i+1)}$ – wartość, w punkcie $x,$ wielomianu stopnia pierwszego przechodzącego przez punkty $(x_{i},y_{i})$ oraz $(x_{i+1},y_{i+1}){:}$

p_{i(i+1)}=P_{i(i+1)}(x)

dla

i=0,\dots ,n-1.

$p_{0\ldots n}$ – wartość, w punkcie $x,$ wielomianu stopnia n-tego przechodzącego przez $(n+1)$ punktów $(x_{i},y_{i}){:}$

p_{0\ldots n}=P_{0\ldots n}(x)

dla

i=0,\dots ,n.

Wielomiany powyższego typu spełniają następującą własność rekurencyjną:

p_{i(i+1)\ldots (i+k)}={\frac {(x-x_{i+k})p_{i(i+1)\ldots (i+k-1)}+(x_{i}-x)p_{(i+1)(i+2)\ldots (i+k)}}{x_{i}-x_{i+k}}},

gdzie: $k$ odpowiada stopniowi wielomianu, $k=1,\dots ,n$ oraz $i=0,\dots ,n.$

Algorytm Neville’a polega na tym, że za pomocą powyższych wzorów konstruujemy tablicę symetryczną, która zawiera wartości wielomianu interpolacyjnego w ustalonym punkcie $x,$ dla $n=3{:}$

$x_{0},y_{0}=p_{0}$
	$p_{01}$
$x_{1},y_{1}=p_{1}$		$p_{012}$
	$p_{12}$		$p_{0123}$
$x_{2},y_{2}=p_{2}$		$p_{123}$
	$p_{23}$
$x_{3},y_{3}=p_{3}$

Kolejne elementy są obliczane rekurencyjnie na podstawie elementów poprzednich.

W praktyce algorytm Neville’a przedstawiamy w nieco innej wersji. Stosując oznaczenia:

t_{(i+k),k}=p_{i(i+1),\dots ,(i+k)}

Tablica przyjmuje postać:

$x_{0},y_{0}=t_{00}$
	$t_{11}$
$x_{1},y_{1}=t_{10}$		$t_{22}$
	$t_{21}$		$t_{33}$
$x_{2},y_{2}=t_{20}$		$t_{32}$
	$t_{31}$
$x_{3},y_{3}=t_{30}$

Ułatwia to komputerowe zaprogramowanie powyższej tablicy (jako tablicy dwuwymiarowej).

Otrzymujemy również wzór rekurencyjny w prostszej postaci:

t_{ik}={\frac {(x-x_{i-k})t_{i,k-1}-(x-x_{i})t_{i-1,k-1}}{x_{i}-x_{i-k}}}

gdzie: $1\leqslant k\leqslant i,$ dla $i=0,1,\dots ,n.$

Pseudokod:

       for i := 0 to n do
           t[i] = f[i]
       for i := i - 1 downto 0 do
           t[j]= t[j + 1] + (t[j + 1] - t[j]) * (x - x[i]) / (x[i] - x[j])

Szukaną wartość wielomianu interpolacyjnego otrzymujemy jako t[0].